package com.aurora.leetcode.answer.dynamic_plan;

/**
 * @author : qiaodan
 * @date : 2025/4/24 19:54
 * @description 62不同路径
 */
public class UniquePaths_62 {


    /**
     * 我的解决方案
     * 动态规划 f(n,m) = f(n,m-1)+f(n-1,m)
     *
     * @param m 高
     * @param n 宽
     * @return
     */
    public int uniquePaths(int m, int n) {
        int[][] mark = new int[n + 1][m + 1];
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                if (i == 1 || j == 1) {
                    mark[i][j] = 1;
                } else {
                    mark[i][j] = mark[i][j - 1] + mark[i - 1][j];
                }
            }
        }
        return mark[n][m];
    }

    public static void main(String[] args) {
        UniquePaths_62 uniquePaths62 = new UniquePaths_62();
        //3,7 28
        //3,2 3
        //7,3 28
        //3,3 6
//        System.out.println(uniquePaths62.uniquePaths(3, 7));
//        System.out.println(uniquePaths62.uniquePaths(3, 2));
//        System.out.println(uniquePaths62.uniquePaths(7, 3));
        System.out.println(uniquePaths62.uniquePaths(3, 3));
    }

}
